package leetcode.code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution18 implements IDebug {

	public List<List<Integer>> fourSum(int[] nums, int target) {
		Arrays.sort(nums);
		List<List<Integer>> ans = new ArrayList<>();
		int len = nums.length;
		for (int i = 0; i < len - 3; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			for (int j = i + 1; j < len - 2; j++) {
				if (j > i + 1 && nums[j] == nums[j - 1]) {
					continue;
				}
				for (int m = j + 1; m < len - 1; m++) {
					if (m > j + 1 && nums[m] == nums[m - 1]) {
						continue;
					}
					for (int n = m + 1; n < len; n++) {
						if (n > m + 1 && nums[n] == nums[n - 1]) {
							continue;
						}
						int sum = nums[i] + nums[j] + nums[m] + nums[n];
						if (sum == target) {
							List<Integer> list = new ArrayList<>();
							list.add(nums[i]);
							list.add(nums[j]);
							list.add(nums[m]);
							list.add(nums[n]);
							ans.add(list);
						}
					}
				}
			}
		}
		return ans;
	}

	public List<List<Integer>> fourSum1(int[] nums, int target) {
		Arrays.sort(nums);
		List<List<Integer>> ans = new ArrayList<>();
		int len = nums.length;
		for (int i = 0; i < len - 3; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			for (int j = i + 1; j < len - 2; j++) {
				if (j > i + 1 && nums[j] == nums[j - 1]) {
					continue;
				}
				int m = j + 1;
				int n = len - 1;
				while (m < n) {
					int sum = nums[i] + nums[j] + nums[m] + nums[n];
					if (sum == target) {
						List<Integer> list = new ArrayList<>();
						list.add(nums[i]);
						list.add(nums[j]);
						list.add(nums[m]);
						list.add(nums[n]);
						ans.add(list);
						do {
							m++;
						} while (m < n && nums[m] == nums[m - 1]);
					} else if (sum > target) {
						do {
							n--;
						} while (n > m && nums[n] == nums[n + 1]);
					} else {
						do {
							m++;
						} while (m < n && nums[m] == nums[m - 1]);
					}
				}
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		// 输入：nums = [1,0,-1,0,-2,2], target = 0
		// 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
		String str = "[1,0,-1,0,-2,2]";
		int[] nums = HelpDebug.str2array3(str);
		int target = 0;
		List<List<Integer>> e = HelpDebug.str2intlist1("[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]");
		List<List<Integer>> r = this.fourSum(nums, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[2,2,2,2,2]";
		int[] nums = HelpDebug.str2array3(str);
		int target = 8;
		List<List<Integer>> e = HelpDebug.str2intlist1("[[2,2,2,2]]");
		List<List<Integer>> r = this.fourSum(nums, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution18 so = new Solution18();
		so.debug1();
		so.debug2();

	}

}
